#include <stdio.h>
#include <assert.h>
#include <iostream>
using namespace std;

typedef char DataType;

struct ListNode
{
    DataType _data;
    ListNode * _next;
    ListNode(DataType value):_data(value),_next(NULL)
    {}
};

ListNode * PushFront(ListNode ** ListHead,DataType value)
{
    assert(ListHead);
    if(*ListHead==NULL)
    {
        *ListHead=new ListNode(value);
        return *ListHead;
    }
    ListNode *new_node=new ListNode(value);
    new_node->_next=*ListHead;
    *ListHead=new_node;
    return new_node;
}

void DeleteDuplication(ListNode **ListHead)
{
    assert(ListHead);
    if(*ListHead==NULL)
    {
        return;
    }
    ListNode *Cur=*ListHead;
    ListNode *Next=*ListHead;
    int IsDelete=false;
    while(Next!=NULL)
    {
        if(Next->_next!=NULL&&Next->_data==Next->_next->_data)
        {
            IsDelete=true;//表明当前的next也是需要删除的
            ListNode *to_delete=Next->_next;
            Next->_next=to_delete->_next;
            delete to_delete;
            continue;
        }
        else//当前的next的数据和next->_next的数据不相同
        {
            if(IsDelete==true)//若当前的next需要删除
            {
                if(*ListHead==Next)//表明头结点时要删除的
                {
                    *ListHead=Next->_next;
                }
                IsDelete=false;//就要重新将标志置为假
                ListNode *to_delete=Next;
                Cur->_next=to_delete->_next;
                Next=Cur->_next;
                delete to_delete;
                continue;
            }
            else
            {
                //表明当前没有要删除的节点
                Cur=Next;
                Next=Next->_next;
            }
        }
    }
}

void ListPrint_char(ListNode *ListHead)
{
    if(ListHead==NULL)
    {
        return;
    }
    ListNode *cur=ListHead;
    while(cur!=NULL)
    {
        printf("%c->",cur->_data);
        cur=cur->_next;
    }
    printf("NULL\n");
}

void DestroyList(ListNode **ListHead)
{
    assert(ListHead);
    if(*ListHead==NULL)
    {
        return;
    }
    ListNode *cur=*ListHead;
    while(cur!=NULL)
    {
        ListNode * to_delete=cur;
        cur=cur->_next;
        delete to_delete;
    }
    *ListHead=NULL;
}
void TestDeleteDuplication()
{
    ListNode *ListHead=NULL;
    PushFront(&ListHead,'e');
    PushFront(&ListHead,'e');
    PushFront(&ListHead,'d');
    PushFront(&ListHead,'c');
    PushFront(&ListHead,'c');
    PushFront(&ListHead,'b');
    PushFront(&ListHead,'a');
    PushFront(&ListHead,'a');
    ListPrint_char(ListHead);
    DeleteDuplication(&ListHead);
    ListPrint_char(ListHead);
    DestroyList(&ListHead);
    ListPrint_char(ListHead);
}

int main()
{
    TestDeleteDuplication();

    return 0;
}
